1. Field of Invention
The present invention is directed to a method and apparatus for designing a packet network that supports Quality of Service.
2. Description of Related Art
There has been a shift in the design of communication networks from diverse data networks, each of which is dedicated to a class of applications, to unified networks, typically utilizing Internet Protocol (IP). As a result, an increased volume of diverse data traffic is being carried over IP networks. For example, the increased traffic may include mission-critical applications such as stock investment transactions and other forms of electronic commerce. The increased traffic may also include other emerging applications, such as voice and video data. Such traffic is sensitive to delay over the network. Accordingly, these applications require better than best-effort IP network service. This represents a change from more long-standing IP applications, such as electronic mail, web browsing and file transfer, which can tolerate considerable delay. Because both delay-sensitive and delay-tolerant applications are being served together, delay-sensitive applications may not receive sufficient resources to satisfy delay requirements.
The invention provides a method and apparatus for designing a network that supports an integrated environment for all types of applications while satisfying individual performance requirements and maintaining high utilization. In one embodiment, an initial network topology is retrieved or created, including links and traffic routing based on a volume of traffic. A maximum delay may then be allocated to each link in the network topology so that the delay limits on node-to-node delay-sensitive communication are satisfied. A bandwidth required for each link is sized, based on a current traffic routing as well as a maximum delay allocated to the link or total link utilization. Link lengths may then be determined and traffic may be rerouted according to shortest paths with respect to the link lengths. These steps are repeated until the network design ceases to change.
Various specific implementations are possible:
Delay allocation, link length and routing may be determined separately for each of different traffic classes and link bandwidths may be sufficiently sized for all of the traffic classes.
The network topology may be systematically examined to determine if eliminating and/or adding any given link would improve the cost, or other relevant metric, of the network.
Maximum delays may further be allocated to the links in proportion to the square root of an imputed cost for each link.
The size of a bandwidth may be determined by assigning virtual channels to each of the traffic classes, with each virtual channel being sized separately; a total bandwidth on the link may be based on the sum of the bandwidths of the virtual channels as well as on a maximum utilization factor for the links.
Link lengths may additionally be determined based on the marginal cost of the link with respect to the total traffic that is routed on it by taking the product of a marginal cost of the bandwidth with respect to current link bandwidth required and a marginal link bandwidth required with respect to the traffic routed on the link.
The same set of link lengths may be used for every class of traffic based on a weighted sum of the link lengths determined separately for each traffic class.